package com.example.javabasic.mianshi;



public class Tiaoshi {


    class TreeNode{
        Integer val ;
        TreeNode left;
        TreeNode right;
        public TreeNode(Integer val){
            this.val = val;
        }
    }

    public static void main(String[] args) {
        int[]  a = {3,9,20,15,7};
        int[] b = {9,3,15,20,7};
        TreeNode test = new Tiaoshi().test(a, b);
        System.out.println(test);

    }

    public  TreeNode test(int[] pre, int[] in){

        if(pre.length ==0 || in.length == 0){
            return null;
        }
        //确认 根节点
        TreeNode  node  = new TreeNode(pre[0]);
        //遍历中序数组
        for(int i = 0;i<in.length;i++){
            //根据中序找出 根节点的左右子树内容
            if(pre[0]== in[i]){
                //左子树内容
                int[] left =  new int[i];
                for(int l = 0;l<i;l++){
                    left[l] = in[i];
                }
                //右子树内容
                int num = in.length-i-1;
                int[] right = new int[num];
                for(int r = 0;r<num;r++){
                    right[r] = in[r+ num-1];
                }
                //递归 左节点 因为 根节点已经取出
                int[] next = new int[pre.length-1];
                for(int x = 0;x<pre.length-1;x++){
                    next[x] = pre[x+1];
                }
                node.left = test(next,left);
                //递归右节点  前序再少一个元素
                int[] nextTwo = new int[pre.length-2];
                for(int x = 0;x< pre.length-2;x++){
                    nextTwo[x] = pre[x+2];
                }
                node.right = test(nextTwo,right);

            }
        }
        return node;
    }

}
